5.7 Checking an Algorithm Analysis


How can you check an Algorithm Analysis?

	measure time empirically
	do times match BigOh prediction



What's the expected increase in time if N doubles in size?

	Linear

		2 times


	Quadratic

		4 times


	Cubic

		8 times



DEMO	(MaxSubSum doubling in size)



Suppose F(N) is the correct Big-Oh function for some algorithm.
What should be true about T(N)/F(N) for various values of N?

	it should converge to positive constant
	converge to zero (F(N) too big)
	diverge (F(N) too small)


DEMO	(Demo.java, convergence to a constant)